# This is s demo for HungarianAlgorithm
from collections import deque


class HungarianAlgorithm(object):
    def __init__(self, graph):
        self.graph = graph
        self.length = len(graph)

    def find(self, x):
        for i in range(self.length):
            if self.graph[x][i] == 1 and not self.used[i]:
                self.used[i] = 1
                # if i don't match any target or i have been match with another x,
                # we should establish the connect between x and i
                if self.match[i] == -1 or self.find(self.match[i]) == 1:
                    self.match[i] = x
                    self.match[x] = i
                    print(x + 1, '->', i + 1)
                    return 1
        return 0

    def Hungarian1(self):
        # The Hungarian Algorithm based on iteration
        self.match = [-1] * self.length
        self.used = [False] * self.length
        m = 0
        for i in range(self.length):
            # Match eatch x:
            if self.match[i] == -1:
                self.used = [False] * self.length
                print("Match target No.{}".format(i + 1))
                m += self.find(i)
        return m

    def Hungarian2(self):
        # The Hungarian based on for loop
        match = [-1] * self.length
        used = [-1] * self.length
        q_list = deque()
        matchNum = 0
        prev = [0] * self.length
        for i in range(self.length):
            if match[i] == -1:  # if target i don't match
                q_list.clear()
                q_list.append(i)
                prev[i] = -1
                flag = False
                while len(q_list) > 0 and not flag:
                    u = q_list.popleft()
                    for j in range(self.length):
                        # u -> target i, j is another object which need to match with i
                        # if i,j don't matched
                        if not flag and self.graph[u][j] == 1 and used[j] != 1:
                            # Match
                            used[j] = i
                            # if i and j is match
                            if match[j] != -1:
                                q_list.append(match[j])
                                prev[match[j]] = u
                            else:
                                flag = True
                                d = u
                                e = j
                                while d != -1:
                                    t = match[d]
                                    match[d] = e
                                    match[e] = d
                                    d = prev[d]
                                    e = t
                                print('match:', match)
                                print('prev', prev)
                                print('deque', q_list)
                if match[i] != -1:
                    matchNum += 1
        return matchNum


graph_1 = [(0, 0, 0, 0, 1, 0, 1, 0),
           (0, 0, 0, 0, 1, 0, 0, 0),
           (0, 0, 0, 0, 1, 1, 0, 0),
           (0, 0, 0, 0, 0, 0, 1, 1),
           (1, 1, 1, 0, 0, 0, 0, 0),
           (0, 0, 1, 0, 0, 0, 0, 0),
           (1, 0, 0, 1, 0, 0, 0, 0),
           (0, 0, 0, 1, 0, 0, 0, 0)]


def do_hungarian1(graph):
    h = HungarianAlgorithm(graph)
    print("biggest match edage number: {}".format(h.Hungarian1()))


def do_hungarian2(graph):
    h = HungarianAlgorithm(graph)
    print("biggest match edage number: {}".format(h.Hungarian2()))


do_hungarian1(graph_1)
do_hungarian2(graph_1)
